#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType lenth;
    ElemType *str;
} SSTable;
//初始化顺序表函数
void SST_Init(SSTable &T, int len) {
    T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
    srand(time(NULL));
    for (int i = 0; i < T.lenth; i++) {
        T.str[i] = rand() % 100;
    }
}
//打印函数
void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

//值交换函数
void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

//分割函数（快排的核心函数）
//挖坑法
int partition(ElemType *str, int low, int high) {
    ElemType pivot = str[low];//拿最左边的作为分割值，并存储下来
    while (low < high) {
        //从后往前遍历，找到一个比分割值小的数
        while (low < high && str[high] >= pivot) high--;
        str[low] = str[high];//将比分割值小的那个数，放到str[low]中
        //从前往后遍历，找到一个比分割值大的数
        while (low < high && str[low] <= pivot) low++;
        str[high] = str[low];//将大的数放到str[high]中,因为刚才high位置的元素已经放到low的位置了
    }
    //最终low==high循环结束，将分割值放到low当前下标所在的元素中即可
    str[low] = pivot;
    //返回分割值所在的下标
    return low;
}

//快速排序
void QuickSort(ElemType *str, int low, int high) {
    if (low < high) {
        int pivot = partition(str, low, high);//pivot用来存储分隔值的位置
        QuickSort(str, low, pivot - 1);//前一半继续递归排序
        QuickSort(str, pivot + 1, high);
    }
}

int main() {
    SSTable T;
    SST_Init(T, 10);
    array_print(T);
    QuickSort(T.str, 0, T.lenth - 1);
    array_print(T);
    return 0;
}
